Introduction

Dynamic programming is an algorithm design paradigm where the problems have optimal substructure and overlapping subproblems. They have specific optimization techniques to solve them faster than usual.

Fibonacci sequence is a good example of dynamic programming problem, we will use it throughout this chapter and several following chapters to explain the fundamental concepts of dynamic programming.

Let $f(n)$ be the $n$-th Fibonacci number, and it is defined as follows:

$$\begin{aligned} f(n) &= f(n-1) + f(n-2) \\ f(0) &= 0 \\ f(1) &= 1 \end{aligned}$$

Which translate to the following recursive function:

n-th Fibonacci Number with Recursion

function fibonacci(n: int) -> int:
    // base cases
    if n == 0: return 0
    if n == 1: return 1

    // recursive case
    return fibonacci(n - 1) + fibonacci(n - 2)

The first few Fibonacci numbers are:

$f(0)$	$f(1)$	$f(2)$	$f(3)$	$f(4)$	$f(5)$	$f(6)$	$f(7)$	$f(8)$	$f(9)$
$0$	$1$	$1$	$2$	$3$	$5$	$8$	$13$	$21$	$34$

Optimal Substructure & Overlapping Subproblems

We will start by explaining the two properties of dynamic programming problems: optimal substructure and overlapping subproblems.

Similar to divide and conquer, dynamic programming problems have optimal substructure, but the difference is that in dynamic programming, the subproblems overlap. These two properties define the dynamic programming problems.

Optimal Substructure

A problem has an optimal substructure if optimal solution of its subproblems can be used to find the optimal solution of the whole problem.

In Fibonacci sequence, $f(n)$ is computed by using $f(n-1)$ and $f(n-2)$. The optimal solutions for $f(n-1)$ and $f(n-2)$ are necessary to compute the optimal solution of $f(n)$, so it has an optimal substructure.

Optimal vs. Correct Solution

Optimal solution is the solution which maximizes efficiency or minimizes cost, while correct solution is the solution which satisfy the constraint of the problem. However, we can use them interchangeably if the problem only has one solution or is already a maximization or minimization problem.

For example, if we want to compute $f(4)$, we need to have the optimal solution for $f(3)$ and $f(2)$ first, which are $2$ and $1$, then we can compute $f(4) = f(3) + f(2) = 2 + 1 = 3$ correctly.

If instead we have the wrong values for a subproblem, let's say the $f(1)$ under $f(3)$ is miscalculated as $0$, then we will obtain the wrong value $f(3) = 1$ and leading to the wrong value $f(4) = 2$.

Optimal substructure shown in $f(4)$. Wrong value for $f(1)$ leading to wrong value for $f(4)$.

Overlapping Subproblems

A problem has overlapping subproblems if its subproblems are reused multiple times throughout the computation of the whole problem.

In Fibonacci sequence, subproblems are reused multiple times. For example, if we expand $f(5)$, we can see that $f(2)$ is reused three times. Since $f(2) = f(1) + f(0)$, so we performed this addition three times in $f(5)$.

$$\begin{aligned} f(5) &= f(4) + f(3) \\ &= (f(3) + f(2)) + (f(2) + f(1)) \\ &= ((\underline{f(2)} + f(1)) + \underline{f(2)}) + (\underline{f(2)} + f(1)) \\ \end{aligned}$$

While carrying out a simple addition may not be a big deal, when the problem size becomes larger, the overhead of repeating the same computation will become significant. For example, the computation $f(100)$ will repeat $f(2)$ 4181 times.

Overlapping subproblems shown in $f(5)$. Same subproblems are colored in the same color. Many subproblems are repeated.

Memoization & Bottom-up Approach

Memoization and bottom-up approach are two common optimization techniques for dynamic programming problems.

While techniques used to solve divide and conquer problems can be applied to dynamic programming problems, they are not as efficient as memoization and bottom-up approach due to the overlapping subproblems.

We will explore how these two techniques optimize the computation of overlapping subproblems.

Memoization

In dynamic programming, memoization is a technique to store the results of the overlapping subproblems.

This makes the number of times the same subproblem need to be calculated only once.

In Fibonacci sequence, before computing anything, we can check if we have already stored the result of the subproblem. If we have, we can just return the result without computing it again.

Bottom-up Approach

In dynamic programming, bottom-up approach is a technique to start solving the problem from the base cases. It can also memoize the results of the subproblems as we go up the recursion tree.

On top of that, it can avoid the overhead of recursion, as function calls are more expensive than results stored in plain variables.

In Fibonacci sequence, we can start from the base cases $f(0)$ and $f(1)$, then compute the next Fibonacci number by using the previous two Fibonacci numbers. We can keep doing this until we reach the $n$-th Fibonacci number.

Most of the time, we want to use the bottom-up approach to solve dynamic programming problems.

Solutions

Here are some notes about the solutions in this topic.

Pseudocode Syntax

We will use the following type annotations for pseudocode:

• int: integer
• float: floating point number (or any number, really)
• bool: boolean
• str: string
• (<type1>, <type2>, ..., <typen>): tuple of <type1>, <type2>, ..., <typen>
• (<name1>: <type1>, <name2>: <type2>, ..., <namen>: <typen>): named tuple
• <type>[]: array or list of <type>

Implementations

In this topic, we will provide pseudocode to the solution, and then language-specific implementations will be provided at the end of each chapter.

Currently, 3 languages are supported: Python, C++, and Rust.